home *** CD-ROM | disk | FTP | other *** search
/ Alde ADA 1: #1 / CCCC 8804 Volume 1 Number 1 - Alde.iso / C / MISC / FUNC / PROFF.ARC / LOOKUP.C < prev    next >
Encoding:
C/C++ Source or Header  |  1988-02-21  |  3.6 KB  |  163 lines
  1. /*
  2.  * from K&R "The C Programming language"
  3.  * Table lookup routines
  4.  *
  5.  */
  6. #include <stdio.h>
  7. #include "proff.h"
  8. /*
  9.  * hash - for a hash value for string s
  10.  *
  11.  */
  12. hash(s)
  13. char *s;
  14. {
  15.    int hashval;
  16.  
  17.    for (hashval = 0; *s != '\0';)
  18.       hashval += *s++;
  19.    return (hashval % HASHMAX);
  20. }
  21.  
  22. /*
  23.  * lookup - lookup for a string s in the hash table
  24.  *
  25.  */
  26. struct hashlist *lookup(s, hashtab)
  27. char *s;
  28. struct hashlist *hashtab[];
  29. {
  30.    struct hashlist *np;
  31.  
  32.    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
  33.       if (strcmp(s, np->name) == 0)
  34.          return (np);                  /* found     */
  35.    return (NULL);                      /* not found */
  36. }
  37.  
  38. /*
  39.  * install - install a string name in hashtable and its value def
  40.  * at a given hashtable.
  41.  */
  42. struct hashlist *install(name, def, hashtab)
  43. char *name;
  44. char *def;
  45. struct hashlist *hashtab[];
  46. {
  47.    int hashval;
  48.    struct hashlist *np, *lookup();
  49.    char *strsave(), *malloc();
  50.  
  51.    if ((np = lookup(name, hashtab)) == NULL)
  52.    {                                   /* not found.. */
  53.       np = (struct hashlist *) malloc(sizeof(*np));
  54.       p_memoryus += sizeof(*np);
  55.       if (np == NULL)
  56.          return (NULL);
  57.       if ((np->name = strsave(name)) == NULL)
  58.          return (NULL);
  59.       hashval = hash(np->name);
  60.       np->next = hashtab[hashval];
  61.       hashtab[hashval] = np;
  62.    }
  63.    else                                /* found..     */
  64.       free(np->def);                   /* free prev.  */
  65.    if ((np->def = strsave(def)) == NULL)
  66.       return (NULL);
  67.    return (np);
  68. }
  69.  
  70. /*
  71.  * strsave - save string s somewhere
  72.  *
  73.  */
  74. char *strsave(s)
  75. char *s;
  76. {
  77.    char *p, *malloc();
  78.    register int n;
  79.  
  80.    n = strlen(s) + 1;
  81.    if ((p = malloc(n)) != NULL)
  82.    {
  83.       p_memoryus += n;
  84.       strcpy(p, s);
  85.    }
  86.    return (p);
  87. }
  88.  
  89. /*
  90.  * lexinstal - instal a string name in hashtable and its value
  91.  *             used by lexical analyser to quickly match a token
  92.  *             and return its lexical value.
  93.  *
  94.  */
  95. struct lexlist *lexinstal(name, val, flag, lextable)
  96. char *name;
  97. int val;
  98. int flag;
  99. struct lexlist *lextable[];
  100. {
  101.    int hashval;
  102.    struct lexlist *np, *lexlook();
  103.    char *strsave(), *malloc();
  104.  
  105.    if ((np = lexlook(name, lextable)) == NULL)
  106.    {                                   /* not found.. */
  107.       np = (struct lexlist *) malloc(sizeof(*np));
  108.       p_memoryus += sizeof(*np);
  109.       if (np == NULL)
  110.          return (NULL);
  111.       if ((np->name = strsave(name)) == NULL)
  112.          return (NULL);
  113.       hashval = hash(np->name);
  114.       np->link = lextable[hashval];
  115.       lextable[hashval] = np;
  116.    }
  117.    np->val = val;                      /* replace prev */
  118.    np->flag = flag;
  119.    return (np);
  120. }
  121.  
  122. /*
  123.  * lexlook - lookup for a string s in the hash table
  124.  *           used by lexinstal only.
  125.  *
  126.  */
  127. struct lexlist *lexlook(s, table)
  128. char *s;
  129. struct lexlist *table[];
  130. {
  131.    struct lexlist *np;
  132.  
  133.    for (np = table[hash(s)]; np != NULL; np = np->link)
  134.       if (strcmp(s, np->name) == 0)
  135.          return (np);                  /* found     */
  136.    return (NULL);                      /* not found */
  137. }
  138.  
  139. /*
  140.  * remove an item from the hash table forever
  141.  *
  142.  */
  143. struct lexlist *remove_item(s, table)
  144. char *s;
  145. struct lexlist *table[];
  146. {
  147.    struct lexlist *np, *xp;
  148.  
  149.    np = table[hash(s)];
  150.    xp = np;
  151.    while (np != NULL)
  152.    {
  153.       if (strcmp(s, np->name) == 0)
  154.       {
  155.          xp->link = np->link;          /* remove the link */
  156.          return (np);                  /* return the lost */
  157.       }
  158.       xp = np;
  159.       np = np->link;
  160.    }
  161.    return (NULL);
  162. }
  163.